package com.lw.leetcode.arr.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 6304. 从一个范围内选择最多整数 I
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/6 9:21
 */
public class MaxCount {

    public static void main(String[] args) {
        MaxCount test = new MaxCount();

        // 2
//        int[] arr = {1, 5, 6};
//        int n = 5;
//        int maxSum = 6;


        // 0
//        int[] arr = {1, 2, 3, 4, 5, 6, 7};
//        int n = 8;
//        int maxSum = 1;

        // 7
        int[] arr = {11};
        int n = 7;
        int maxSum = 50;

        int i = test.maxCount(arr, n, maxSum);
        System.out.println(i);
    }

    public int maxCount(int[] banned, int n, int maxSum) {
        Arrays.sort(banned);
        int i = 1;
        int j = 0;
        int count = 0;
        int sum = 0;
        int length = banned.length;
        while (i <= n && j < length) {
            if (i == banned[j]) {
                i++;
                j++;
            } else if (i > banned[j]) {
                j++;
            } else {
                count++;
                sum += i;
                i++;
                if (sum > maxSum) {
                    return count - 1;
                }
            }
        }
        while (i <= n) {
            count++;
            sum += i;
            i++;
            if (sum > maxSum) {
                return count - 1;
            }
        }
        return count;
    }

}
